#include <malloc.h>
#include <memory.h>

#ifdef NDEBUG
#undef NDEBUG
#include <assert.h>
#define NDEBUG
#else
#include <assert.h>
#endif

#include "../include/forward_list.h"

struct forward_list_node
{
    void* __data;
    struct forward_list_node* __next;
};



/*
 * forward_list_node interface
*/

inline struct forward_list_node* forward_list_node__construct(void* data, struct forward_list_node* next)
{
    struct forward_list_node* new_list_node = (struct forward_list_node*)malloc(sizeof(struct forward_list_node));

    assert("Memory allocation error" && new_list_node);

    new_list_node->__data = data;
    new_list_node->__next = next;

    return new_list_node;
}



/*
 * forward_list interface
*/

inline size_t get_forward_list_struct_size()
{
    return sizeof(struct forward_list);
}

inline void forward_list__construct(struct forward_list* list)
{
    assert("Passing NULL pointer to struct" && list);

    list->__head = NULL;
    list->__tail = NULL;
    list->__size = 0;
    list->__node_destructor = NULL;
}

inline void forward_list__destruct(struct forward_list* const list)
{
    forward_list__clear(list);
}

void forward_list__copy(struct forward_list* dst, struct forward_list* const src)
{
    if (!forward_list__is_empty(dst))
    {
        forward_list__destruct(dst);
    }

    struct forward_list_node* node = src->__head;
    while (node = node->__next, node->__next)
    {
        forward_list__add_back(dst, node->__data);
    }
}

void forward_list__swap(struct forward_list* lhs, struct forward_list* rhs)
{
    assert("Attempting to swap with self" && lhs->__head != rhs->__head);

    struct forward_list tmp;
    memcpy(&tmp, rhs, sizeof(struct forward_list));
    memcpy(rhs, lhs, sizeof(struct forward_list));
    memcpy(lhs, &tmp, sizeof(struct forward_list));
}

void forward_list__remove_front(struct forward_list* list)
{
    assert("List is empty, nothing to remove" && !forward_list__is_empty(list));

    struct forward_list_node* node_to_destruct = list->__head;
    list->__head = list->__head->__next;

    if (list->__node_destructor)
    {
        list->__node_destructor(node_to_destruct);
    }

    free(node_to_destruct);
    list->__size--;
}

void forward_list__remove_back(struct forward_list* list)
{
    assert("List is empty, nothing to remove" && !forward_list__is_empty(list));

    struct forward_list_node* list_node = list->__head;
    while (list_node = list_node->__next, list_node->__next->__next)
        ;

    struct forward_list_node* node_to_destruct = list_node->__next;
    list_node->__next = list_node->__next->__next;
    list->__tail = list_node;

    if (list->__node_destructor)
    {
        list->__node_destructor(node_to_destruct);
    }

    free(node_to_destruct);
    list->__size--;
}

inline void forward_list__clear(struct forward_list* const list)
{
    while (!forward_list__is_empty(list))
    {
        forward_list__remove_front(list);
    }
}

void forward_list__add_front(struct forward_list* list, void* data)
{
    struct forward_list_node* new_list_node = forward_list_node__construct(data, list->__head);

    list->__head = new_list_node;
    if (!list->__tail)
    {
        list->__tail = list->__head;
    }

    list->__size++;
}

void forward_list__add_back(struct forward_list* list, void* data)
{
    if (forward_list__is_empty(list))
    {
        forward_list__add_front(list, data);
    }
    else
    {
        list->__tail->__next = forward_list_node__construct(data, NULL);
        list->__tail = list->__tail->__next;
        list->__size++;
    }
}

void forward_list__merge_back(struct forward_list* dst, struct forward_list* const src)
{
    assert("Source list is empty, nothing to merge" && !forward_list__is_empty(src));

    struct forward_list new_list_part;
    forward_list__construct(&new_list_part);
    forward_list__swap(&new_list_part, src);
    forward_list__destruct(src);

    dst->__tail->__next = new_list_part.__head;
    dst->__tail = new_list_part.__tail;
    dst->__size += forward_list__size(&new_list_part);
}

void forward_list__merge_front(struct forward_list* dst, struct forward_list* const src)
{
    assert("Source list is empty, nothing to merge" && !forward_list__is_empty(src));

    struct forward_list new_list_part;
    forward_list__construct(&new_list_part);
    forward_list__swap(&new_list_part, src);
    forward_list__destruct(src);

    new_list_part.__tail->__next = dst->__head;
    dst->__head = new_list_part.__head;
    dst->__size += forward_list__size(&new_list_part);
}

void forward_list__remove_at(struct forward_list* list, forward_list_iterator_t pos)
{
    if (pos == forward_list__begin(list))
    {
        forward_list__remove_front(list);
    }
    else if (pos == forward_list__end(list) || !(*pos)->__next)
    {
        forward_list__remove_back(list);
    }
    else
    {
        struct forward_list_node* node_to_destruct = *pos;
        *pos = (*pos)->__next;
        if (list->__node_destructor)
        {
            list->__node_destructor(node_to_destruct);
        }
        free(node_to_destruct);
        list->__size--;
    }
}

inline void forward_list__remove_after(struct forward_list* list, forward_list_iterator_t pos)
{
    if (*pos)
    {
        forward_list_iterator__next(&pos);
    }
    forward_list__remove_at(list, pos);
}

void forward_list__insert_at(struct forward_list* list, void* data, forward_list_iterator_t pos)
{
    if (pos == forward_list__begin(list))
    {
        forward_list__add_front(list, data);
    }
    else if (pos == forward_list__end(list) || !(*pos)->__next)
    {
        forward_list__add_back(list, data);
    }
    else
    {
        *pos = forward_list_node__construct(data, *pos);
        list->__size++;
    }
}

inline void forward_list__insert_after(struct forward_list* list, void* data, forward_list_iterator_t pos)
{
    if (*pos)
    {
        forward_list_iterator__next(&pos);
    }
    forward_list__insert_at(list, data, pos);
}

void forward_list__merge_at(struct forward_list* dst, struct forward_list* const src, forward_list_iterator_t pos)
{
    if (pos == forward_list__begin(dst))
    {
        forward_list__merge_front(dst, src);
    }
    else if (pos == forward_list__end(dst) || !(*pos)->__next)
    {
        forward_list__merge_back(dst, src);
    }
    else
    {
        struct forward_list new_list_part;
        forward_list__construct(&new_list_part);
        forward_list__swap(&new_list_part, src);
        forward_list__destruct(src);

        new_list_part.__tail->__next = *pos;
        *pos = new_list_part.__head;

        dst->__size += forward_list__size(&new_list_part);
    }
}

inline void forward_list__merge_after(struct forward_list* dst, struct forward_list* const src, forward_list_iterator_t pos)
{
    if (*pos)
    {
        forward_list_iterator__next(&pos);
    }
    forward_list__merge_at(dst, src, pos);
}


/*
 * forward_list getters and setters
*/

inline size_t forward_list__size(struct forward_list* const list)
{
    return list->__size;
}

inline int forward_list__is_empty(struct forward_list* const list)
{
    return list->__head == NULL;
}

inline void* forward_list__get_at(struct forward_list* const list, size_t index)
{
    return *forward_list__get_at_addr(list, index);
}

inline void* forward_list__get_front(struct forward_list* const list)
{
    return *forward_list__get_front_addr(list);
}

inline void* forward_list__get_back(struct forward_list* const list)
{
    return *forward_list__get_back_addr(list);
}

inline const void* forward_list__get_at_const(struct forward_list* const list, size_t index)
{
    return (const void*)(*forward_list__get_at_addr(list, index));
}

inline const void* forward_list__get_front_const(struct forward_list* const list)
{
    return (const void*)(*forward_list__get_front_addr(list));
}

inline const void* forward_list__get_back_const(struct forward_list* const list)
{
    return (const void*)(*forward_list__get_back_addr(list));
}

void** forward_list__get_at_addr(struct forward_list* const list, size_t index)
{
    assert("Index out of range" && index < forward_list__size(list));

    if (index == 0)
    {
        return forward_list__get_front(list);
    }
    else if (index == (forward_list__size(list) - 1))
    {
        return forward_list__get_back(list);
    }
    else
    {
        struct forward_list_node* node = list->__head;
        while (node = node->__next, index--)
            ;
        return &node->__data;
    }
}

inline void** forward_list__get_front_addr(struct forward_list* const list)
{
    assert("Dereference NULL pointer (no data)" && list->__head);
    return &list->__head->__data;
}

inline void** forward_list__get_back_addr(struct forward_list* const list)
{
    assert("Dereference NULL pointer (no data)" && list->__tail);
    return &list->__tail->__data;
}

inline const void** forward_list__get_at_addr_const(struct forward_list* const list, size_t index)
{
    return (const void**)forward_list__get_at_addr(list, index);
}

inline const void** forward_list__get_front_addr_const(struct forward_list* const list)
{
    return (const void**)forward_list__get_front_addr(list);
}

inline const void** forward_list__get_back_addr_const(struct forward_list* const list)
{
    return (const void**)forward_list__get_back_addr(list);
}

inline void forward_list__set_node_destructor(struct forward_list* list, forward_list_node_destructor_t node_destructor)
{
    list->__node_destructor = node_destructor;
}

inline forward_list_iterator_t forward_list__begin(struct forward_list* const list)
{
    return &list->__head;
}

inline forward_list_iterator_t forward_list__end(struct forward_list* const list)
{
    return &list->__tail->__next;
}

forward_list_iterator_t __forward_list__find_impl(struct forward_list* const list, void* data, size_t type_size)
{
    forward_list_iterator_t iter = forward_list__begin(list);
    for (; iter != forward_list__end(list) && memcmp(forward_list_iterator__extract_data_addr(iter), &data, type_size);
         forward_list_iterator__next(&iter))
        ;
    return iter;
}

forward_list_iterator_t forward_list__find_if(struct forward_list* const list, int(*predicate)(void* data))
{
    forward_list_iterator_t iter = forward_list__begin(list);
    for (; iter != forward_list__end(list) && !predicate(forward_list_iterator__extract_data(iter));
         forward_list_iterator__next(&iter))
        ;
    return iter;
}



/*
 * forward_list iterator functions
*/

inline struct forward_list_node* __forward_list_iterator__get_ptr(forward_list_iterator_t iter)
{
    return *iter;
}

inline forward_list_iterator_t forward_list_iterator__next(forward_list_iterator_t* iter)
{
    *iter = &(**iter)->__next;
    return *iter;
}

inline forward_list_iterator_t forward_list_iterator__advance(forward_list_iterator_t* iter, size_t n)
{
    while (forward_list_iterator__next(iter), --n)
        ;
    return *iter;
}

inline void* forward_list_iterator__extract_data(forward_list_iterator_t iter)
{
    return *forward_list_iterator__extract_data_addr(iter);
}

inline void** forward_list_iterator__extract_data_addr(forward_list_iterator_t iter)
{
    return &(*iter)->__data;
}
